package com.hardy.basic;

import java.util.*;

/**
 * Author: Hardy
 * Date:   2021/1/20
 * Description:
 **/
public class Str {
    // 3. 无重复字符的最长子串
    public int lengthOfLongestSubstring(String s) {
        int i = 0;
        int j = 0;
        int max = 0;
        Set<Character> cache = new HashSet<>();

        while (j < s.length()) {
            char c = s.charAt(j);

            if (cache.contains(c)) {
                cache.remove(s.charAt(i++));
            } else {
                cache.add(c);
                max = Math.max(max, cache.size());
                j++;
            }
        }
        return max;
    }

    // 1143. 最长公共子序列
    public int longestCommonSubsequence(String text1, String text2) {
        int m = text1.length(), n = text2.length();
        int[][] dp = new int[m + 1][n + 1]; // 记录当前坐标下，最长公共子序列

        // 转移方程 dp[i + 1][j + 1] = Math.max(dp[i + 1][j], dp[i][j + 1]);
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                // 获取两个串字符
                char c1 = text1.charAt(i), c2 = text2.charAt(j);
                if (c1 == c2) {
                    // 去找它们前面各退一格的值加1即可
                    dp[i + 1][j + 1] = dp[i][j] + 1;
                } else {
                    //要么是text1往前退一格，要么是text2往前退一格，两个的最大值
                    dp[i + 1][j + 1] = Math.max(dp[i + 1][j], dp[i][j + 1]);
                }
            }
        }
        return dp[m][n];
    }

    // 5. 最长回文子串
    public String longestPalindrome(String s) {
        int idx = 0;
        int len = 0;

        int l = s.length();
        boolean[][] dp = new boolean[l][l]; // 是不是当前长度是不是回文窜

        // dp[i][j] = s[i]==s[j] && dp[i+1][j-1] // i,j 代表左右边界
        for (int j = 0; j < l; j++) {
            for (int i = 0; i <= j; i++) {
                dp[i][j] = s.charAt(i) == s.charAt(j) && (j - i <= 2 || dp[i + 1][j - 1]);
                if (dp[i][j] && len < (j - i + 1)) {
                    idx = i;
                    len = j - i + 1;
                }
            }
        }
        print(dp);
        return s.substring(idx, idx + len);
    }

    // 93. 复原IP地址
    public List<String> restoreIpAddresses(String s) {
        List<String> res = new ArrayList<String>();

        char[] chars = s.toCharArray();
        StringBuilder sb = new StringBuilder();

        for (int i = 0; i < chars.length; i++) {
            sb.append(chars[i]);
            if (!checkIp(sb.toString())) break;

            StringBuilder sbj = new StringBuilder();
            for (int j = i + 1; j < chars.length; j++) {
                sbj.append(chars[j]);
                if (!checkIp(sbj.toString())) break;

                StringBuilder sbk = new StringBuilder();
                for (int k = j + 1; k < chars.length; k++) {
                    sbk.append(chars[k]);
                    if (!checkIp(sbk.toString())) break;

                    StringBuilder sbl = new StringBuilder();
                    for (int l = k + 1; l < chars.length; l++) {
                        sbl.append(chars[l]);
                        if (!checkIp(sbl.toString())) break;
                        if (l != chars.length - 1) continue;

                        StringBuilder r = new StringBuilder();
                        r.append(sb).append(".").append(sbj).append(".").append(sbk).append(".").append(sbl);
                        res.add(r.toString());
                    }
                }
            }
        }
        return res;
    }

    // 131. 分割回文串
    public List<List<String>> partition(String s) {
        List<List<String>> res = new LinkedList<>();

        // 二分拆分
        for (int idx = 1; idx < s.length(); idx++) {
            // 第一部分
            if (!check(s, 0, idx - 1)) continue;

            // 第二部分 继续拆
            List<List<String>> rs = partition(s.substring(idx, s.length()));

            if (rs.isEmpty()) continue;

            String prev = s.substring(0, idx);
            for (List<String> r : rs) {
                ((LinkedList<String>) r).addFirst(prev);
                res.add(r);
            }
        }

        // 整个字符串检查
        if (check(s, 0, s.length() - 1)) {
            List<String> r = new LinkedList<>();
            r.add(s);
            res.add(r);
        }
        return res;
    }

    // 28. 实现 strStr()
    public int strStr(String haystack, String needle) {
        // abebcabch
        Map<Character, Integer> map = getSunday(needle);
        int l = needle.length();

        // 匹配 haystack[i] needle[j]
        for (Integer i = l - 1, j = i; j != null && l - j + i <= haystack.length(); ) {
            // 检查当前字符串匹配
            if (haystack.charAt(i) == needle.charAt(j))
                if (check(haystack, i - j, needle, 0, l)) return i - j;

            // 计算偏移量
            for (j = null; j == null && i + 1 < haystack.length(); ) j = map.get(haystack.charAt(++i));
        }
        return -1;
    }

    // 1047. 删除字符串中的所有相邻重复项
    public String removeDuplicates(String s) {
        if (s == null || s.length() == 0) return "";

        StringBuilder sb = new StringBuilder();

        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            // 重复
            if (sb.length() > 0 && sb.charAt(sb.length() - 1) == c) {
                sb.deleteCharAt(sb.length() - 1);
                continue;
            }

            // 不重复
            sb.append(c);
        }
        return sb.toString();
    }

    public Map<Character, Integer> getSunday(String needle) {
        Map<Character, Integer> map = new HashMap<>();
        for (int i = needle.length() - 1; i >= 0; i--) {
            map.putIfAbsent(needle.charAt(i), i);
        }
        return map;
    }

    public boolean check(String a, int i, String b, int j, int l) {
        for (l = l + i; i < l; i++, j++) {
            if (a.charAt(i) != b.charAt(j)) return false;
        }
        return true;
    }

    public boolean check(String s, int i, int j) {
        if (i == j) return true;
        for (; i < j; i++, j--) {
            if (s.charAt(i) != s.charAt(j)) return false;
        }
        return true;
    }

    public boolean checkIp(String s) {
        if (s.length() > 3) return false;
        if (s.length() > 1 && s.charAt(0) == '0') return false;
        int val = Integer.valueOf(s);
        return val >= 0 && val <= 255;
    }

    public void print(boolean[][] arr) {
        for (boolean[] a : arr) {
            System.out.println(Arrays.toString(a));
        }
    }

    public int[] getKMP(String s) {
        // aabaaf
        char[] chars = s.toCharArray();
        int[] next = new int[chars.length];
        next[0] = -1;

        for (int i = 1, j = -1; i < chars.length; i++) {

            while (j >= 0 && chars[i] != chars[j + 1]) {
                j = next[j];
            }

            if (chars[i] == chars[j + 1]) j++;

            next[i] = j;
        }
        return next;
    }

    // 76. 最小覆盖子串
    public String minWindow(String s, String t) {
        Map<Character, Integer> m1 = new HashMap<>();
        Map<Character, Integer> m2 = new HashMap<>();

        // 统计字符出现次数
        for (int i = 0; i < t.length(); i++) {
            m1.put(t.charAt(i), m1.getOrDefault(t.charAt(i), 0) + 1);
        }

        int l1 = m1.size();
        int l2 = 0;

        int idx = 0;
        int len = Integer.MAX_VALUE;

        for (int i = 0, j = 0; j < s.length(); j++) {
            char c = s.charAt(j);
            if (!m1.containsKey(c)) continue;

            // 收集统计
            m2.put(c, m2.getOrDefault(c, 0) + 1);
            if (m2.get(c) == m1.get(c)) l2++;

            // 满足覆盖
            while (l1 == l2) {
                if (len > j - i) {
                    idx = i;
                    len = j - i;
                }
                c = s.charAt(i++);
                if (!m2.containsKey(c)) continue;

                int x = m2.get(c) - 1;
                m2.put(c, x);

                if (x < m1.get(c)) l2--;
            }
        }
        return len == Integer.MAX_VALUE ? "" : s.substring(idx, idx + len + 1);
    }


    public static void main(String[] args) {
        Str main = new Str();

        //List<String> list = main.restoreIpAddresses("25525511135");
        //System.out.println(list);

        //main.partition("aab");

        //main.longestPalindrome("cbbd");

        //main.getKMP("aabaaf");

        //main.strStr("mississippi", "issipi");

        int[] a = {1, 2, 2, 3};
        int[] b = {1, 2, 2, 3, 0, 0, 0, 0, 0, 0};

        //int t = 1234;
        //char[] chars = Integer.toString(t).toCharArray();

        //HashMap<Object, Object> map = new HashMap<>();
        //map.getOrDefault("", "");
        //map.containsKey();

        //Integer.MAX_VALUE

        //System.out.println(main.minWindow("ADOBECODEBANC", "ABC"));
        System.out.println(main.removeDuplicates("abbaca"));
    }
}
